//
// Writer: Zooper
//
// Date  : 17.04.2006
//

#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <iomanip.h>
#include <stdlib.h>

//*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*
typedef struct st
{
  int dann;
  struct st *next;
}QUEUE;

QUEUE *front = NULL;
QUEUE *rear = NULL;
int k = 0;

//*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*
             //1  2  3  4  5
int row1[5] = {0 ,50,-1,10,-1};
int row2[5] = {50,0 ,-1,-1,20};
int row3[5] = {-1,-1,0 ,6 ,15};
int row4[5] = {10,-1,6 ,0 ,-1};
int row5[5] = {-1,20,15,-1,0 };

int* map[5] = {row1, row2, row3, row4, row5};

//*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*
void Qinsert(int a)
{
  QUEUE	*q;
  q = new QUEUE;
  if (k == 0)
  {
    front = q;
  }
  else
  {
    rear->next = q;
  }
  q->dann = a;
  rear = q;

  rear->next = NULL;
  k++;
}

int Qdelete(void)
{
  QUEUE *q;
  int temp;
  if (front == NULL)
  {
    cout <<endl <<"empty!";
  }
  else
  {
    temp = rear->dann;
    q = front->next;
    delete front;
    front = q;
    k--;
  }
  return temp;
}

void Qclear(void)
{
  QUEUE *q;
  while (front != NULL)
  {
    q = front->next;
    delete front;
    front = q;
    k--;
  }
}

//*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*
void display(int **data)
{
  for (int i=0; i<5; i++)
  {
    for (int j=0; j<5; j++)
    {
      cout <<setw(3) <<data[i][j]; // *(*(data+i)+j)
    }
    cout <<endl;
  }
  cout<<endl;
}

int visited[5];
void breadth_first_search(void)
{
  while (front != NULL)
  {
    int w = Qdelete();
    if (visited[w-1] == 0)
    {
      visited[w-1] = 1;
      cout << w << " ";
      for (int i=0; i<5; i++)
      {
        if (map[w-1][i] != -1 && map[w-1][i] != 0)
        {
          Qinsert(i+1);
        }
      }
    }
  }
}

//*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*
void main(void)
{
  clrscr();
  for (int k=0; k<5; k++)
  {
    visited[k] = 0;
  }
  Qinsert(1);
  breadth_first_search();
  Qclear();
  getch();
}

